#include<stdio.h>
#include<iostream>
using namespace std;

//存储结构----记录序列以顺序表存储 
#define InfoType char
#define MAXSIZE 20   //设记录不超过20个
typedef int KeyType; //设关键字为整型量(int 型)
typedef struct{  //定义每个记录(数据元素)的结构  
	KeyType key; //关键字 
	InfoType otherinfo; //其它数据项 
} RedType; //Record Type 
typedef struct{ //定义顺序表的结构 
	RedType r[MAXSIZE + 1]; //存储顺序表的向量  //r[0]一般作为哨兵或缓冲区 
	int length; //顺序表的长度 
}SqList;



//1.简单选择排序：在待排序的数据中选出最大(小)的元素放在最终的位置 
void SelectSort(SqList &L){
	for(int i = 1; i < L.length; i++){
		int k = i;
		for(int j = i+1; j < L.length; j++){
			if(L.r[j].key < L.r[k].key) k = j; //记录最小值的位置 
		}
		if(k!=i){ //交换 
			RedType temp = L.r[i];
			L.r[i] = L.r[k];
			L.r[k] = temp;
		}
	}
}


//2.堆排序(nlogn)
//堆；小根堆，大根堆 
//实现堆排序需要解决两个问题：
//1.如何由一个无序序列构建成一个堆
//2.如何在输出堆顶元素后,调整剩余元素为一个新的堆

//对小根堆而言； 
//(1)输出堆顶元素之后, 以堆中最后一个元素代替之; 
//(2)然后将根节点值与左、右子树的根节点值进行比较, 并与其中小者进行交换; 
//(3)重复上述操作, 直至叶子结点, 将得到新的堆, 称这个从堆顶至叶子的调整过程为 "筛选" 

//"筛选"过程的算法描述如下：
void HeapAdjust(elem R[], int s, int m){
	//已知R[s...m]中记录的关键字除R[s]之外均满足堆的定义, 本函数调整R[s]的关键字, 使R[s...m]成为一个 大根堆
	elem rc = R[s];
	for(int j = 2 * s; j < m; j *= 2){//沿key较大的孩子结点向下筛选 
		if(j < m && R[j] < R[j+1]) ++j; //j为key较大的记录的下标
		if(rc >= R[j]) break;
		R[s] = R[j]; s = j; //rc应插入在位置s上 
	} //for 
	R[s] = rc; //插入 
}//HeapAdjust

//堆的建立
//将初始无序的R[1]到R[n]建成一个小根堆, 可用以下语句实现:
/*
for(i =  n/2; i >= 1; i--)
	HeapAdjust(R, i, n); 
*/


//堆排序算法如下：
void HeapSort(elem R[]){//对R[1]到R[n]进行堆排序 
	int i;
	for(i = n/2; i >= 1; i--)
		HeapAdjust(R, i, n); //建初始堆
	for(i = n; i > 1; i--){//进行n-1趟排序 
		Swap(R[1], R[i]); //根与最后一个元素交换
		HeapAdjust(R, 1, i-1); //对R[1]到R[i-1]重新建堆 
	} 
} //HeapSort





